package 树与图.字典树;

import java.util.HashMap;
import java.util.Map;

/**
 * 105 : 前序和中序遍历序列构造二叉树
 * 思路分析：构建二叉树的问题通过前序遍历和中序遍历的结果来解决，前序遍历的顺序是：左--根--右， 中序遍历的结果：根--左--右
 * 这意味着，前序遍历中的第一个元素一定是根节点，而在中序遍历中，根节点将序列分割为左右两部分，左子树和右子树。
 * 算法思路：
 *  1. 前序遍历的第一个元素是根节点；
 *  2. 在中序遍历中找到根节点，然后确定左子树和右子树的中序遍历。
 *  3. 利用左子树和右子树的长度可以在前序遍历中分割出左子树和右子树的前序遍历。
 *  4. 递归构建左子树和右子树，然后返回根节点。
 * @Author lf
 * @Date 3/25/2024
 */
public class L105leftMidTree {
    // 记录中序遍历中节点值与索引的映射
    private Map<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 建立中序遍历的节点值和索引映射，以便于快速定位到根节点
        indexMap = new HashMap<>();
        for (int i = 0; i < n; i++){
            indexMap.put(inorder[i],i);
        }
        return buildSubTree(preorder,inorder,0,n-1,0,n-1);
    }

    /**
     * 递归构建二叉树
     * @param preorder
     * @param inorder
     * @param preLeft 左序遍历的左边界
     * @param preRight 左序遍历的右边界
     * @param inLeft 中序遍历的左边界
     * @param inRight 中序遍历的右边界
     * @return
     */
    private TreeNode buildSubTree(int[] preorder, int[] inorder,int preLeft,int preRight,int inLeft,int inRight){
        if(preLeft > preRight){
            return null;
        }
        // 前序遍历的第一个节点就是根节点
        int rootVal = preorder[preLeft];
        TreeNode treeNode = new TreeNode(rootVal);
        // 在中序遍历中定位根节点的位置
        int rootIndex = indexMap.get(rootVal);
        // 左子树的个数
        int leftCount = rootIndex - inLeft;
        // 递归构建左子树和右子树
        // 左子树，前序遍历的左半部分和中序遍历的左半部分
        treeNode.left = buildSubTree(preorder,inorder,preLeft+1,preLeft+leftCount,inLeft,rootIndex-1);
        // 右子树，前序遍历的右边部分和中序遍历的右半部分
        treeNode.right = buildSubTree(preorder, inorder,preLeft+leftCount+1,preRight,rootIndex+1,inRight);
        return treeNode;
    }

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

}